package _14_链表中倒数第k个节点;
/**
 * 题目描述
 * 输入一个链表，输出该链表中倒数第k个结点。
 */


/**
 * 用一趟，快慢指针，快指针先走k-1步，然后和慢指针一起走，直到快指针的next为null，则slow为结果
 *注意边界条件，当head为空和k<=0时，返回null，此外当在快指针走k-1步时，fast.next为null，说明k大于链表长度，反回Null
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) return null;
        ListNode fast = head;
        ListNode slow = head;
        int n = 0;
        //快指针先走k-1个间隔，n从0变到k-1,一共k-1步（k-1个间隔）
        while (n < k - 1) {
            if (fast.next != null) {
                fast = fast.next;
                n++;
            } else return null;
        }
        //一起走
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
